package com.czk.sort;

import java.util.Arrays;

/**
 * 冒泡排序的实现
 * @Author:ChenZhangKun
 * @Date: 2020/6/25 15:29
 */
public class BubbleSort {
    public static void main(String[] args) {
        //
        int[] array={2,5,8,4,6,2,1,3,9,10,15,11,7};
        bubbleSort_1(array);
        bubbleSort_2(array);

        int[] ints=new int[80000];
        for (int i = 0; i <80000 ; i++) {
            ints[i]=(int) (Math.random()*8000000);
        }
        // 测试排序时间
        long l = System.currentTimeMillis();
        bubbleSort_2(ints);
        long l1 = System.currentTimeMillis();
        System.out.println((l1-l)/1000);
    }

    /**
     * 普通的冒泡排序
     * @param array
     */
    public static void bubbleSort_1(int[] array){
        int temp=0;
        for (int i = 0; i <array.length-1 ; i++) {
            // 每次循环找出最大值
            for (int j = 0; j <array.length-i-1 ; j++) {
                // 交换变量的值
                if (array[j]>array[j+1]){
                    temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }

    /**
     * 冒泡排序的优化
     * 加入是否交换的标记
     * @param array
     */
    public static void bubbleSort_2(int[] array){
        int temp=0;
        // 交换标记，有交换则置为true
        boolean flag=false;
        for (int i = 0; i <array.length-1 ; i++) {
            // 每次循环找出最大值
            for (int j = 0; j <array.length-i-1 ; j++) {
                // 交换变量的值
                if (array[j]>array[j+1]){
                    flag=true;
                    temp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=temp;
                }
            }
            // 没有交换，数组有序，直接退出
            if (!flag){
                break;
            }else {
                // 交换过郭，重新置为false
                flag=false;
            }
        }
        //System.out.println(Arrays.toString(array));
    }

}
